// Copyright (C) 2011  Andrew H. Chan
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

#ifndef _DIFFERENCECOVERSAMPLE_H__
#define _DIFFERENCECOVERSAMPLE_H__

#include <iostream>
#include <sstream>
#include <vector>
#include <assert.h>

#include "ntSeq.hpp"

typedef unsigned long long uint64;

//std::string getSuffix(std::vector<uint64> const &s, uint64 index) {
//    std::ostringstream ostr;
//    for(uint64 ii=index; ii<s.size(); ++ii) ostr << s[ii] << " ";
//    return ostr.str();
//}

class DCS {
    public:
        DCS(ntSeq const &T, uint64 logV);

        void computeDifferenceCover(uint64 desiredV); // initialize DC 
        void computeDelta(); // initialize d
        void computeRank(); // initialize rank and h
        void computeISA(ntSeq const &T); // modifies l
        void multiQsort(ntSeq const &T, std::vector<uint64> &Dn, uint64 charIndex, uint64 index, uint64 length); // modifies l

        uint64 mu(uint64 k) const {
            uint64 j = k/v;
            uint64 di = k%v;
            uint64 i = rank[di];
            return (n/v) * i + std::min(i,h+1) + j; 
        }

        // (i-j) mod v
        inline uint64 modDiff(uint64 a, uint64 b) const {
            return (a-b) & vMask;
            //if(a>=b) return (a-b)%v;
            //else return v-(b-a)%v;
        }

        inline uint64 delta(uint64 i, uint64 j) const {
            return modDiff(d[modDiff(j,i)],i);
        }

        inline bool lt(uint64 i, uint64 j) const {
            uint64 tmpDelta = delta(i,j);
            if(l[mu(i+tmpDelta)] < l[mu(j+tmpDelta)]) return true;
            else return false;
        }

        inline bool lte(uint64 i, uint64 j) const {
            uint64 tmpDelta = delta(i,j);
            if(l[mu(i+tmpDelta)] <= l[mu(j+tmpDelta)]) return true;
            else return false;
        }

        inline bool eq(uint64 i, uint64 j) const {
            uint64 tmpDelta = delta(i,j);
            if(l[mu(i+tmpDelta)] == l[mu(j+tmpDelta)]) return true;
            else return false;
        }

        inline bool gte(uint64 i, uint64 j) const {
            uint64 tmpDelta = delta(i,j);
            if(l[mu(i+tmpDelta)] >= l[mu(j+tmpDelta)]) return true;
            else return false;
        }

        inline bool gt(uint64 i, uint64 j) const {
            uint64 tmpDelta = delta(i,j);
            if(l[mu(i+tmpDelta)] > l[mu(j+tmpDelta)]) return true;
            else return false;
        }

        inline uint64 packedKey(ntSeq const &T, uint64 index) const {
            uint64 tmp=0;
            uint64 maxii = std::min(index+v, std::min(index+21,(uint64)T.size()));
            for(uint64 ii=index; ii<maxii; ++ii) tmp |= (uint64)(T.get(ii)+1) << (3*(20-(ii-index)%21));
            assert(index < T.size()+21+1); // need to allow for empty suffix and charIncr can add up to 21 to index 
            return tmp;
        }


        int verifyDC() const;
        int verifyDelta() const;
        int verifyDCS(ntSeq const &T, std::vector<uint64> const &s) const;

        // hard-coded difference covers
        static const uint64 dc0[];
        static const uint64 dc1[];
        static const uint64 dc2[];
        static const uint64 dc3[];
        static const uint64 dc4[];
        static const uint64 dc5[];
        static const uint64 *dcAll[];
        static const uint64 dcSize[];

        // fields
        uint64 n; // length of T
        uint64 logV;
        uint64 v;
        uint64 vMask;
        std::vector<uint64> DC; // array of length about sqrt(v)
        std::vector<uint64> d; // array of length v; used to compute delta
        std::vector<uint64> l; // array of length about n/sqrt(v)
        std::vector<uint64> rank; // array of length v
        uint64 h; // index in DC of n%v; used to compute mu

        class Compare {
            public:
                Compare(DCS const &dcs) : dcs(dcs) {}
                bool operator()(uint64 a, uint64 b) const {
                    if(dcs.lt(a,b)) return true;
                    else return false;
                }
                DCS const &dcs;
        };
};

#endif
